SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Gregory Chaitin</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Gregory Chaitin</span></span>

</h1>

</header>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox biography vcard"><tbody><tr><th colspan="2" class="infobox-above" style="font-size:125%;"><div class="fn">Gregory Chaitin</div></th></tr><tr><td colspan="2" class="infobox-image"><div class="infobox-caption">Chaitin in 2008</div></td></tr><tr><th scope="row" class="infobox-label">Born</th><td class="infobox-data"><span style="display:none"> (<span class="bday">1947-06-25</span>) </span>25 June 1947<br><div style="display:inline" class="birthplace"><a href="Chicago" title="Chicago">Chicago</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></div></td></tr><tr><th scope="row" class="infobox-label">Nationality</th><td class="infobox-data category"><a href="Argentina" title="Argentina">Argentine</a>-<a href="United_States" title="United States">American</a></td></tr><tr><th scope="row" class="infobox-label">Known for</th><td class="infobox-data"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style><div class="plainlist"><ul><li><a href="Algorithmic_Information_Theory" class="mw-redirect" title="Algorithmic Information Theory">Algorithmic Information Theory</a></li><li><a href="Chaitin's_constant" title="Chaitin's constant">Chaitin's constant</a></li><li><a href="Chaitin's_algorithm" title="Chaitin's algorithm">Chaitin's algorithm</a></li></ul></div></td></tr><tr><td colspan="2" class="infobox-full-data"><b>Scientific career</b></td></tr><tr><th scope="row" class="infobox-label">Fields</th><td class="infobox-data category"><div class="plainlist"><ul><li><a href="Biology" title="Biology">Biology</a></li><li><a href="Mathematics" title="Mathematics">Mathematics</a></li><li><a href="Computer_science" title="Computer science">Computer science</a></li></ul></div></td></tr><tr><th scope="row" class="infobox-label">Institutions</th><td class="infobox-data"><div class="plainlist">

<ul><li><a href="Mohammed_VI_Polytechnic_University" class="mw-redirect" title="Mohammed VI Polytechnic University">Mohammed VI Polytechnic University</a></li>

<li><a href="Federal_University_of_Rio_de_Janeiro" title="Federal University of Rio de Janeiro">Federal University of Rio de Janeiro</a></li>

<li><a href="University_of_Buenos_Aires" title="University of Buenos Aires">University of Buenos Aires</a></li>

<li><a href="IBM_T.J._Watson_Research_Center" class="mw-redirect" title="IBM T.J. Watson Research Center">IBM T.J. Watson Research Center</a></li></ul>

</div></td></tr><tr style="display:none"><td colspan="2">

</td></tr><tr><th scope="row" class="infobox-label">Website</th><td class="infobox-data"><span class="url"><a rel="nofollow" class="external text" href="https://uba.academia.edu/GregoryChaitin">uba<wbr>.academia<wbr>.edu<wbr>/GregoryChaitin</a></span></td></tr></tbody></table>

<p><b>Gregory John Chaitin</b> (<span class="rt-commentedText nowrap"><span class="IPA nopopups noexcerpt" lang="en-fonipa">/<span style="border-bottom:1px dotted"><span title="/ˈ/: primary stress follows">ˈ</span><span title="/tʃ/: 'ch' in 'China'">tʃ</span><span title="/aɪ/: 'i' in 'tide'">aɪ</span><span title="'t' in 'tie'">t</span><span title="/ɪ/: 'i' in 'kit'">ɪ</span><span title="'n' in 'nigh'">n</span></span>/</span></span> <i title="English pronunciation respelling"><span style="font-size:90%">CHY</span>-tin</i>; born 25 June 1947) is an <a href="Argentina" title="Argentina">Argentine</a>-<a href="United_States" title="United States">American</a> <a href="Mathematician" title="Mathematician">mathematician</a> and <a href="Computer_scientist" title="Computer scientist">computer scientist</a>. Beginning in the late 1960s, Chaitin made contributions to <a href="Algorithmic_information_theory" title="Algorithmic information theory">algorithmic information theory</a> and <a href="Metamathematics" title="Metamathematics">metamathematics</a>, in particular a computer-theoretic result equivalent to <a href="G%C3%B6del's_incompleteness_theorem" class="mw-redirect" title="Gödel's incompleteness theorem">Gödel's incompleteness theorem</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> He is considered to be one of the founders of what is today known as algorithmic (Solomonoff–Kolmogorov–Chaitin, Kolmogorov or program-size) <a href="Kolmogorov_complexity" title="Kolmogorov complexity">complexity</a> together with <a href="Andrei_Kolmogorov" class="mw-redirect" title="Andrei Kolmogorov">Andrei Kolmogorov</a> and <a href="Ray_Solomonoff" title="Ray Solomonoff">Ray Solomonoff</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Along with the works of e.g. <a href="Solomonoff" class="mw-redirect" title="Solomonoff">Solomonoff</a>, <a href="Kolmogorov" class="mw-redirect" title="Kolmogorov">Kolmogorov</a>, <a href="Per_Martin-L%C3%B6f" title="Per Martin-Löf">Martin-Löf</a>, and <a href="Leonid_Levin" title="Leonid Levin">Leonid Levin</a>, <a href="Algorithmic_information_theory" title="Algorithmic information theory">algorithmic information theory</a> became a foundational part of <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, <a href="Information_theory" title="Information theory">information theory</a>, and <a href="Mathematical_logic" title="Mathematical logic">mathematical logic</a>.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> It is a common subject in several computer science curricula. Besides computer scientists, Chaitin's work draws attention of many philosophers and mathematicians to fundamental problems in mathematical creativity and digital philosophy.

</p>

<div class="mw-heading mw-heading2"><h2 id="Mathematics_and_computer_science">Mathematics and computer science</h2></div>

<p>Gregory Chaitin is <a href="Jewish" class="mw-redirect" title="Jewish">Jewish</a>. He attended the <a href="Bronx_High_School_of_Science" title="Bronx High School of Science">Bronx High School of Science</a> and the <a href="City_College_of_New_York" title="City College of New York">City College of New York</a>, where he (still in his teens) developed the theory that led to his independent discovery of <a href="Kolmogorov_complexity" title="Kolmogorov complexity">algorithmic complexity</a>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>Chaitin has defined <a href="Chaitin's_constant" title="Chaitin's constant">Chaitin's constant</a> Ω, a <a href="Real_number" title="Real number">real number</a> whose digits are <a href="Normal_number" title="Normal number">equidistributed</a> and which is sometimes informally described as an expression of the probability that a random program will halt. Ω has the mathematical property that it is <a href="Definable_number" class="mw-redirect" title="Definable number">definable</a>, with asymptotic approximations from below (but not from above), but not <a href="Computability_theory_(computation)" class="mw-redirect" title="Computability theory (computation)">computable</a>.

</p><p>Chaitin is also the originator of using <a href="Graph_coloring" title="Graph coloring">graph coloring</a> to do <a href="Register_allocation" title="Register allocation">register allocation</a> in <a href="Compiling" class="mw-redirect" title="Compiling">compiling</a>, a process known as <a href="Chaitin's_algorithm" title="Chaitin's algorithm">Chaitin's algorithm</a>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>He was formerly a researcher at IBM's Thomas J. Watson Research Center in New York. He has written more than 10 books that have been translated to about 15 languages. He is today interested in questions of metabiology and <a href="Information_theory" title="Information theory">information-theoretic</a> formalizations of the theory of <a href="Evolution" title="Evolution">evolution</a>, and is a member of the Institute for Advanced Studies at <a href="Mohammed_VI_Polytechnic_University" class="mw-redirect" title="Mohammed VI Polytechnic University">Mohammed VI Polytechnic University</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Other_scholarly_contributions">Other scholarly contributions</h2></div>

<p>Chaitin also writes about <a href="Philosophy" title="Philosophy">philosophy</a>, especially <a href="Metaphysics" title="Metaphysics">metaphysics</a> and <a href="Philosophy_of_mathematics" title="Philosophy of mathematics">philosophy of mathematics</a> (particularly about epistemological matters in mathematics). In metaphysics, Chaitin claims that <a href="Algorithmic_information_theory" title="Algorithmic information theory">algorithmic information theory</a> is the key to solving problems in the field of <a href="Biology" title="Biology">biology</a> (obtaining a formal definition of 'life', its origin and <a href="Evolution" title="Evolution">evolution</a>) and <a href="Neuroscience" title="Neuroscience">neuroscience</a> (the problem of <a href="Consciousness" title="Consciousness">consciousness</a> and the study of the mind).

</p><p>In recent writings, he defends a position known as <a href="Digital_physics" title="Digital physics">digital philosophy</a>. In the <a href="Epistemology" title="Epistemology">epistemology</a> of mathematics, he claims that his findings in <a href="Mathematical_logic" title="Mathematical logic">mathematical logic</a> and algorithmic information theory show there are "mathematical facts that are true for no reason, that are true by accident".<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Chaitin proposes that mathematicians must abandon any hope of proving those mathematical facts and adopt a <a href="Quasi-empirical" class="mw-redirect" title="Quasi-empirical">quasi-empirical</a> methodology.

</p>

<div class="mw-heading mw-heading2"><h2 id="Honors">Honors</h2></div>

<p>In 1995 he was given the degree of doctor of science <i><a href="Honoris_causa" class="mw-redirect" title="Honoris causa">honoris causa</a></i> by the <a href="University_of_Maine" title="University of Maine">University of Maine</a>. In 2002 he was given the title of honorary professor by the <a href="University_of_Buenos_Aires" title="University of Buenos Aires">University of Buenos Aires</a> in Argentina, where his parents were born and where Chaitin spent part of his youth. In 2007 he was given a Leibniz Medal<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> by <a href="Wolfram_Research" title="Wolfram Research">Wolfram Research</a>. In 2009 he was given the degree of doctor of philosophy <i>honoris causa</i> by the <a href="National_University_of_C%C3%B3rdoba" title="National University of Córdoba">National University of Córdoba</a>. He was formerly a researcher at <a href="IBM" title="IBM">IBM</a>'s <a href="Thomas_J._Watson_Research_Center" title="Thomas J. Watson Research Center">Thomas J. Watson Research Center</a> and a professor at the <a href="Federal_University_of_Rio_de_Janeiro" title="Federal University of Rio de Janeiro">Federal University of Rio de Janeiro</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div>

<ul><li><i>Information, Randomness & Incompleteness</i> (<a href="World_Scientific" title="World Scientific">World Scientific</a> 1987) (<a rel="nofollow" class="external text" href="https://books.google.com/books?id=dDbE2lNiHjkC&dq=Chaitin+G.J.+%281975%29+Randomness+and+Mathematical+Proof.&pg=PA3">online</a>)</li>

<li><i>Algorithmic Information Theory</i> (<a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a> 1987) (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20111215170328/http://www.cs.auckland.ac.nz/~chaitin/cup.pdf">online</a>)</li>

<li><i>Information-theoretic Incompleteness</i> (<a href="World_Scientific" title="World Scientific">World Scientific</a> 1992) (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20100514220011/http://www.cs.auckland.ac.nz/~chaitin/ps3.pdf">online</a>)</li>

<li><i>The Limits of Mathematics</i> (<a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a> 1998) (<a rel="nofollow" class="external text" href="https://www.academia.edu/99397030/The_Limits_of_Mathematics_A_Course_on_Information_Theory_and_the_Limits_of_Formal_Reasoning_Springer_Verlag_1998_">online</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230425213929/https://www.academia.edu/99397030/The_Limits_of_Mathematics_A_Course_on_Information_Theory_and_the_Limits_of_Formal_Reasoning_Springer_Verlag_1998_">Archived</a> 25 April 2023 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>)</li>

<li><i>The Unknowable</i> (<a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a> 1999) (<a rel="nofollow" class="external text" href="https://www.academia.edu/92235376/LISP_A_Formalism_for_Expressing_Mathematical_Algorithms_Springer_Verlag_1999_">online</a>)</li>

<li><i>Exploring Randomness</i> (<a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a> 2001) (<a rel="nofollow" class="external text" href="https://www.academia.edu/43381055/The_number_of_n_bit_strings_with_maximum_complexity_is_random_Springer_Verlag_2001_">online</a>)</li>

<li><i>Conversations with a Mathematician</i> (<a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a> 2002) (<a rel="nofollow" class="external text" href="https://www.academia.edu/100602330/The_Creative_Life_Conversations_with_a_Mathematician_Springer_Verlag_2002_">online</a>)</li>

<li><i>From Philosophy to Program Size</i> (<a rel="nofollow" class="external text" href="http://ioc.ee/">Tallinn Cybernetics Institute</a> 2003)</li>

<li><i>Meta Math!: The Quest for Omega</i> (<a href="Pantheon_Books" title="Pantheon Books">Pantheon Books</a> 2005) (reprinted in UK as <i>Meta Maths: The Quest for Omega</i>, <a href="Atlantic_Books" title="Atlantic Books">Atlantic Books</a> 2006) (<style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0404335">math/0404335</a></span>)</li>

<li><i>Teoria algoritmica della complessità</i> (<a rel="nofollow" class="external text" href="http://www.giappichelli.it/">G. Giappichelli Editore</a> 2006)</li>

<li><i>Thinking about Gödel & Turing</i> (<a href="World_Scientific" title="World Scientific">World Scientific</a> 2007) (<a rel="nofollow" class="external text" href="https://www.academia.edu/100314710/Thinking_about_Gödel_and_Turing_Essays_on_Complexity_1970_2007_World_Scientific_2007_">online</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230429215701/https://www.academia.edu/100314710/Thinking_about_G%C3%B6del_and_Turing_Essays_on_Complexity_1970_2007_World_Scientific_2007_">Archived</a> 29 April 2023 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>)</li>

<li><i>Mathematics, Complexity and Philosophy</i> (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20120425234032/http://www.editorialmidas.es/">Editorial Midas</a> 2011)</li>

<li><i>Gödel's Way</i> (<a href="CRC_Press" title="CRC Press">CRC Press</a> 2012)</li>

<li><i>Proving Darwin: Making Biology Mathematical</i> (<a href="Pantheon_Books" title="Pantheon Books">Pantheon Books</a> 2012) (<a rel="nofollow" class="external text" href="https://www.academia.edu/43376660/A_mathematical_theory_of_evolution_and_biological_creativity_CDMTCS_2011_">online</a>)</li>

<li><i>Philosophical Mathematics: Infinity, Incompleteness, Irreducibility</i> (<a href="Academia.edu" title="Academia.edu">Academia.edu</a> 2024) (<a rel="nofollow" class="external text" href="https://www.academia.edu/122592748/PHILOSOPHICAL_COMPUTATIONS_Reflections_on_the_fiftieth_anniversary_of_the_halting_probability_2024_">online</a>)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.umcs.maine.edu/~chaitin/60.pdf">Gregory Chaitin (2007), Algorithmic information theory: "Chaitin Research Timeline"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120323024501/http://www.umcs.maine.edu/~chaitin/60.pdf">Archived</a> 23 March 2012 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://archive.siam.org/pdf/news/830.pdf">Review of Meta Math!: The Quest for Omega, By Gregory Chaitin</a> SIAM News, Volume 39, Number 1, January/February 2006</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Panu Raatikainen, "Exploring Randomness and The Unknowable"

<a rel="nofollow" class="external text" href="https://www.ams.org/notices/200109/rev-panu.pdf"><i>Notices</i> of the American Mathematical Society</a> Book Review October 2001.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFCalude2002" class="citation book cs1">Calude, C.S. (2002). <i>Information and Randomness: An Algorithmic Perspective</i>. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">R. Downey, and D. Hirschfeldt (2010), <i>Algorithmic Randomness and Complexity</i>, Springer-Verlag.</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFLiVitanyi1997" class="citation cs2">Li; Vitanyi (1997), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=LKEmB_GQ53QC"><i>An Introduction to Kolmogorov Complexity and Its Applications</i></a>, Springer, p. 92, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780387948683</bdi>, <q>G.J.Chaitin had finished the Bronx High School of Science, and was an 18-year-old undergraduate student at City College of the City University of New York, when he submitted two papers.... In his [second] paper, Chaitin puts forward the notion of Kolmogorov complexity....</q></cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFChaitin1966" class="citation cs2">Chaitin, G. J. (October 1966), "On the Length of Programs for Computing Finite Binary Sequences", <i>Journal of the ACM</i>, <b>13</b> (4): <span class="nowrap">547–</span>569, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321356.321363">10.1145/321356.321363</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207698337">207698337</a></cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">G.J. Chaitin, <i>Register Allocation and Spilling via Graph Coloring</i>, <a rel="nofollow" class="external text" href="https://patents.google.com/patent/US4571678">US Patent 4,571,678</a> (1986) [cited from <a rel="nofollow" class="external text" href="http://ssw.jku.at/Teaching/PhDTheses/Hoflehner/index.html"><i>Register Allocation on the Intel® Itanium® Architecture</i></a>, p.155]</span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFChaitin2003" class="citation arxiv cs1">Chaitin, G. J. (2003). "From Philosophy to Program Size". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0303352">math/0303352</a></span>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">Zenil, Hector "Leibniz medallion comes to life after 300 years"

<a rel="nofollow" class="external text" href="http://www.mathrix.org/liquid/archives/the-history-of-the-chaitin-leibniz-medallion"><i>Anima Ex Machina</i>, The Blog of Hector Zenil</a>, 3 November 2007.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite class="citation cs2 cs1-prop-foreign-lang-source">Pagallo, Ugo (2005), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110722034613/http://www.giappichelli.it/home/88-348-5635-X,3485635.asp1"><i>Introduzione alla filosofia digitale. Da Leibniz a Chaitin</i></a> [<i>Introduction to Digital Philosophy: From Leibniz to Chaitin</i>] (in Italian), G. Giappichelli Editore, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-88-348-5635-2</bdi>, archived from <a rel="nofollow" class="external text" href="http://www.giappichelli.it/home/88-348-5635-X,3485635.asp1">the original</a> on 22 July 2011<span class="reference-accessdate">, retrieved <span class="nowrap">16 April</span> 2008</span></cite></li>

<li><cite class="citation cs2">Calude, Cristian S., ed. (2007), <i>Randomness and Complexity. From Leibniz to Chaitin</i>, World Scientific, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-981-277-082-0</bdi></cite></li>

<li><cite id="CITEREFWuppuluriDoria2020" class="citation cs2">Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), <i>Unravelling Complexity: The Life and Work of Gregory Chaitin</i>, World Scientific, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2F11270">10.1142/11270</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-981-12-0006-9</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:198790362">198790362</a></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox">

<div class="side-box-text plainlist">Wikiquote has quotations related to <i><b><a href="https://en.wikiquote.org/wiki/Special:Search/Gregory_Chaitin" class="extiw external" title="q:Special:Search/Gregory Chaitin">Gregory Chaitin</a></b></i>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="https://ufrj.academia.edu/GregoryChaitin">G J Chaitin Home Page from academia.edu</a></li>

<li><a rel="nofollow" class="external text" href="http://cs.umaine.edu/~chaitin/">G J Chaitin Home Page from UMaine.edu in the Internet Archive</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131029184916/http://cs.umaine.edu/~chaitin/">Archived</a> 29 October 2013 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li><a rel="nofollow" class="external text" href="https://ufrj.academia.edu/GregoryChaitin">List of publications of G J Chaitin</a></li>

<li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=RlYS_GiAnK8"><span class="">Video of lecture on metabiology: "Life as evolving software"</span></a> on <a href="YouTube_video_(identifier)" class="mw-redirect" title="YouTube video (identifier)">YouTube</a></li>

<li><a rel="nofollow" class="external text" href="http://videolectures.net/ephdcs08_chaitin_lcai/">Video of lecture on "Leibniz, complexity and incompleteness"</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20060510171405/http://www.dc.uba.ar/people/profesores/becher/ns.html">New Scientist article (March, 2001) on Chaitin, Omegas and Super-Omegas</a></li>

<li><a rel="nofollow" class="external text" href="http://www.flownet.com/gat/chaitin.html">A short version of Chaitin's proof</a></li>

<li><a rel="nofollow" class="external text" href="https://www.whyarewehere.tv/people/gregory-chaitin/">Gregory Chaitin extended film interview and transcripts for the 'Why Are We Here?' documentary series</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/mew-cx/chaitin_lisp">Chaitin Lisp on github</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1038841319">

/* start https://en.wikipedia.org/ */

.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q930837#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata3431" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q930837#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata3431" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">International</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://isni.org/isni/0000000108782113">ISNI</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://viaf.org/viaf/22226140">VIAF</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.worldcat.org/fast/201205">FAST</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.oclc.org/worldcat/entity/E39PBJkT6YfXBcHhj9rXqDFMyd">WorldCat</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/121658600">Germany</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/n87875505">United States</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb12399405t">France</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb12399405t">BnF data</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.ndl.go.jp/auth/ndlna/00846981">Japan</a></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Chaitin, Gregory J."><a rel="nofollow" class="external text" href="https://opac.sbn.it/nome/VIAV104134">Italy</a></span></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=pna2015853949&CON_LNG=ENG">Czech Republic</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://datos.bne.es/resource/XX5283065">Spain</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="http://data.bibliotheken.nl/id/thes/p07330655X">Netherlands</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://catalogue.nlg.gr/cgi-bin/koha/opac-authoritiesdetail.pl?authid=308211">Greece</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://libris.kb.se/c9prtc4w4k3pnm7">Sweden</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://dbn.bn.org.pl/descriptor-details/9810610110305606">Poland</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007302467305171">Israel</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://cantic.bnc.cat/registre/981058528531406706">Catalonia</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://opac.kbr.be/LIBRARY/doc/AUTHORITY/14026762">Belgium</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Academics</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://ci.nii.ac.jp/author/DA01727376?l=en">CiNii</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.mathgenealogy.org/id.php?id=193825">Mathematics Genealogy Project</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://zbmath.org/authors/?q=ai:chaitin.gregory-j">zbMATH</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://dblp.org/pid/c/GJChaitin">DBLP</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet/MRAuthorID/46985">MathSciNet</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Artists</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Gregory Chaitin"><a rel="nofollow" class="external text" href="https://musicbrainz.org/artist/2c9ca272-4023-414f-88cd-69edeca42b6e">MusicBrainz</a></span></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.deutsche-biographie.de/121658600.html?language=en">Deutsche Biographie</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.deutsche-digitale-bibliothek.de/person/gnd/121658600">DDB</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.idref.fr/03309263X">IdRef</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/person/c9e4e21b-a66e-4ef6-b90a-9cb345fa3bf7">Yale LUX</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-27" href="https://en.wikipedia.org/wiki/?title=Gregory_Chaitin&oldid=1272057549">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>